// Package day_12_dp 1-509
// @Title day_12_dp
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/6 13:50
// @Create  2021/9/6 13:50
package day_12_dp

// 简单题 求一个数组的斐波拉契数

func FibDP(n int) int {
	if n < 2 {
		return 0
	}
	// 创建DP数组
	dpArr := make([]int, n)
	dpArr[0] = 1
	dpArr[1] = 1
	for i := 2; i < n; i++ {
		dpArr[i] = dpArr[i-1] + dpArr[i-2]
	}
	return dpArr[n-1]
}

// 因为我们考虑到 dp数组中的每一个元素都之和前两个元素有关，所以我们可以不用考虑创建数组，实现将空间复杂度降到O(1)

func FibDpPlus(n int) int {
	// 1. 特殊值判断 (特判)
	if n < 2 {
		return n
	}
	slow, fast := 0, 1 // 一开始初始化两个变量，表示第一，和第二个元素
	ans := 0
	// 从第三步开始，往后循环，依次覆盖
	for i := 2; i <= n; i++ {
		ans = slow + fast
		slow = fast
		fast = ans
	}
	return ans
}
